package sword.chapter4LinkList;

/**
 * 排序的循环链表
 * <p>
 * 细节
 * 1. 没有节点head=null情况；一个节点head.next=null情况；大于一个节点的情况
 * 2. while循环的条件 A：val不在cur cur.next之间 B：没有转完一圈 cur.next != head（转到最后一个节点时，cur.next == head跳出循环）
 * 3. 最大值节点的判断，作用：如果插入的是一个比环内任一节点都大的值，A条件true B条件false，那应该在最大值节点后面加入插入的值
 * 4. 赋值：A false时，插入到cur cur.next之间 B false时，插入到最大值节点后面
 *
 * @author K
 * @date 2021-11-30 19:40
 */
public class S29Insert {

    public static Node s29(Node head, int val) {
        if (head == null) {
            Node node = new Node(val);
            node.next = node;
            return node;
        } else if (head.next == head) {
            Node node = new Node(val);
            head.next = node;
            node.next = head;
            return head;
        } else {
            return insertCore(head, val);
        }
    }

    public static Node insertCore(Node head, int val) {
        Node node = new Node(val);
        Node cur = head;
        Node biggest = head;

        while (!(cur.val <= val && val <= cur.next.val) && cur.next != head) {
            cur = cur.next;
            if (biggest.val <= cur.val) {
                biggest = cur;
            }
        }

        if (cur.val <= val && val <= cur.next.val) {
            Node next = cur.next;
            cur.next = node;
            node.next = next;
        } else {
            Node next = biggest.next;
            biggest.next = node;
            node.next = next;
        }
        return head;
    }

    public static void main(String[] args) {
        Node nodeA = new Node(3);
        Node node5 = new Node(5);
        Node node1 = new Node(1);
        nodeA.next = node5;
        node5.next = node1;
        node1.next = nodeA;

        Node nodeB1 = new Node(1);
        Node nodeB2 = new Node(2);
        Node nodeB3 = new Node(3);
        Node nodeB4 = new Node(4);
        Node nodeB5 = new Node(5);
        Node nodeB6 = new Node(6);

        nodeB1.next = nodeB2;
        nodeB2.next = nodeB3;
        nodeB3.next = nodeB4;
        nodeB4.next = nodeB5;
        nodeB5.next = nodeB6;
        nodeB6.next = nodeB1;

//        Node result = s29(nodeA, 0);
        Node result2 = s29(nodeB1, 7);
        System.out.println();
    }
}
